__author__ = 'st316'
'''
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
'''


class Solution:
    # @return a boolean
    def isValid(self, s):
        if not s:
            return True
        if len(s) % 2 != 0:
            return False
        d = {'(': ')', '{': '}', '[': ']'}
        stack = [s[0]]
        for i in xrange(1, len(s)):
            if stack and stack[-1] in d and d[stack[-1]] == s[i]:
                stack.pop()
            else:
                stack.append(s[i])
        return False if stack else True


if __name__ == '__main__':
    s = Solution()
    print s.isValid("([])")
